package com.sam;

/**
 *
 *  N皇后问题是一个经典的问题，在一个N*N的棋盘上放置N个皇后，每行一个并使其不能互相攻击（同一行、同一列、同一斜线上的皇后都会自动攻击）。
 *
 * Created by samwang on 2017/11/24.
 */
public class NQueen {
    public static void main(String[] args) {

        nQueenRecursion(8);

    }

    /**
     *  递归解决方案
     * @param n n个皇后
     */
    static void nQueenRecursion(int n){
        nQueenRecursion(0, n, new int[n]);
    }

    static int x = 0;
    /**
     * 递归解决方案 : 调用示例
     * <p>
     * 假设在o~k-1行的皇后已经排列好了
     *
     * @param k
     * queenPos 前k-1摆放的位置
     */
    private static void nQueenRecursion(int k,int n, int[] queenPos) {
        int i;
        if (k == n) {//已摆好
            for (i = 0; i < n; i++) {
                System.out.print((queenPos[i] + 1) + " ");
            }
            System.out.println(" " + x++);
        } else {
            for (i = 0; i < n; i++) {//第K行，N列，看要选哪一列(i表示第K个)
                int j;
                for (j = 0; j < k; j++) {//与前K个判断，是否冲突
                    if (queenPos[j] == i || Math.abs(queenPos[j] - i) == Math.abs(k - j)) {//处于同一列或者处于对角线
                        break;
                    }
                }
                if (j == k) {//没冲突
                    queenPos[k] = i;
                    nQueenRecursion(k + 1, n, queenPos);

                }

            }

        }

    }



}
